package com.tucc.hello.leetcode.no1_400.no1_200.no81_100.no89;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        for (int i = 0; i <= 13; i++) {
            System.out.println("============" + i + "============");
            System.out.println(solution.grayCode(i));
        }
    }

    List<Integer> firstResult = new ArrayList<>();

    public List<Integer> grayCode(int n) {
        int max = (int) Math.pow(2, n);
        List<Integer> andNums = new ArrayList<>();
        int num = 1;
        for (int i = 1; i <= n; i++) {
            andNums.add(num);
            num <<= 1;
        }
        boolean[] visit = new boolean[max];
        List<Integer> result = new ArrayList<>();
        result.add(0);
        visit[0] = true;
        grayCode(max, 0, visit, result, andNums);
        return firstResult;
    }


    public void grayCode(int max, int cur, boolean[] visit, List<Integer> result,
                         List<Integer> andNums) {
        if (result.size() == max) {
            firstResult = new ArrayList<>(result);
        } else {
            List<Integer> nextList = nextGrayCode(cur, max, visit, andNums);
            for (int next : nextList) {
                result.add(next);
                visit[next] = true;
                grayCode(max, next, visit, result, andNums);
                if (firstResult.size() != 0) {
                    return;
                }
                result.remove(result.size() - 1);
                visit[next] = false;
            }
        }
    }

    public List<Integer> nextGrayCode(int cur, int max, boolean[] visit, List<Integer> andNums) {
        List<Integer> nextList = new ArrayList<>();
        for (int andNum : andNums) {
            int next = 0;
            if ((cur & andNum) == 0) {
                next = cur + andNum;
            } else {
                next = cur - andNum;
            }
            if (!visit[next]) {
                nextList.add(next);
            }
        }
        return nextList;
    }
}
